package com.lihepeng.leecode.classic;

/**
 * 链表环路检测
 *
 * @author lihepeng
 * 给定一个有环链表，实现一个算法返回环路的开头节点。
 * 有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。
 */
public class DetectCycle {
    // 快慢指针法
    public ListNode detectCycle(ListNode head) {
        ListNode s = head;
        ListNode f = head;
        while (true) {
            s = s.next;
            f = f.next.next;
            if (s == f) {
                return s;
            }
            if (s.next == null) {
                return null;
            }

        }

    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
